Home Up

Home Teaching Glossary ARM Processors Supplements Prof issues About

Parallel Processing Problems

Question 1

What are the advantages and disadvantages of parallel processing over serial processing? Your answer should begin with a criticism of this question.

Solution

This question is flawed in the sense that it does not define the term parallel processing. Consider a computer with a single core CPU. Does that perform serial processing? No, it doesn’t. Instruction execution is overlapped (pipelining) and that itself implements a form of parallelism. Moreover, the various subsystems (display, Ethernet interface, disk interface, audio controller) will inevitably all have their own embedded special-purpose processors. The so-called serial processor is already a de facto parallel processor.

However, this type of question is really asking about the class of parallel processor where the main CPU itself is replicated either as multiple cores on one chip, or multiple processors on one motherboard, or multiple processors in multiple systems.

Parallel processing allows you to divide a problem into parts, allocate individual parts to processors, perform operations in parallel, and then merge the individual results to create the final result. The favorite example of multiprocessing is weather forecasting because you can partition the atmosphere into as many cells as you want and then let a processor work on the climate of its own cell. Parallel processing has become possible because (a) we can do it economically by including multiple CPUs on one silicon chip and (b) we have to do it because we have reached the limit at which we can clock chips and still remove the waste heat.

The problem with parallel computing is that there is no simple way of decomposing a task into n subtasks. Some problems are very difficult to decompose into individual tasks and these cannot exploit the hardware of a parallel processor. Moreover, highly parallel processing requires complex inter-processor communications (more buses, arbitration networks, and caches). Some believe that parallel processing is a temporary measure that we are forced to put up with while we are waiting for something better to come along.

Question 2

By how much can we speed up the evaluation of F = a2 + b2 + c2 if addition and subtraction take the same time?

Solution

We can’t do any of the additions until at least two squares have been performed. We can carry out the squares in parallel

Step 1: Evaluate a2, b2, and c2 at the same time.

Step 2: We can add a2 + b2 to get a subtotal

Step 3: We can add c2 to the subtotal to get a2 + b2 + c2.

This reduces the number of steps in the serial case from 5 to three, giving a speed up of 5/3 = 1.67.

We could do better if we designed a 3-input adder to sum the three squares in one operation. This would give a speedup of 5/2 = 2.5.